/*****************************************************
Copyright (C) 2020. All rights reserved.
File name     ：BubbleSort.c
Version       ：v1.0
Author        ：zhengqijun
Date          ：2020-04-09
Function List ：
Description   ：Bubble Sort
******************************************************/

#include "BubbleSort.h"
#include <stdbool.h>

// Static Function Lists
static void Swap(ElementType *Lhs, ElementType *Rhs);

static void Swap(ElementType *Lhs, ElementType *Rhs) {
    ElementType Tmp;

    Tmp = *Lhs;
    *Lhs = *Rhs;
    *Rhs = Tmp;
}

void BubbleSort(ElementType A[], int N) {
    int i;
    int j;

    for (i = 0; i < N; ++i) {
        for (j = 0; j < N - i - 1; ++j) {
            if (A[j] > A[j + 1]) {
                Swap(&A[j], &A[j + 1]);
            }
        }
    }
}

// Improved Version 1
void BubbleSort1(ElementType A[], int N) {
    int i;
    int j;
    bool flag;  // set flag

    for (i = 0; i < N - 1; ++i) {
        flag = false;
        for (j = 0; j < N - 1 - i; ++j) {
            if (A[j] > A[j + 1]) {
                Swap(&A[j], &A[j + 1]);
                flag = true;
            }
        }

        if (!flag) {
            return;
        }
    }
}

// Improved Version 2
void BubbleSort2(ElementType A[], int N) {
    int i;
    int j;
    int flag;

    flag = N;
    while (flag > 0) {
        j = flag;
        flag = 0;
        for (i = 0; i < j - 1; ++i) {
            if (A[i] > A[i + 1]) {
                Swap(&A[i], &A[i + 1]);
                flag = i + 1;
            }
        }
    }
}

// EOF

